#ifndef ALGO_H_
#define ALGO_H_

#include <algorithm>
#include <charconv>
#include <cmath>
#include <cstdint>
#include <string>
#include <vector>

namespace
{
constexpr int MAX = ~(1 << 31);
// n : 一共几个技能
// i : 当前来到了第几号技能
// r : 怪兽目前的剩余血量
inline int skill(int r, int i, int n, std::vector<int>& x, std::vector<int>& y)
{
    if (r <= 0) return i;
    if (i == n) return MAX;

    auto swap = [&x, &y](int i, int j) {
        int x_temp = x[i];
        x[i]       = x[j];
        x[j]       = x_temp;
        int y_temp = y[i];
        y[i]       = y[j];
        y[j]       = y_temp;
    };

    int ans = MAX;
    for (int j = i; j < n; j++) {
        swap(i, j);
        int rr = r > y[i] ? r - x[i] : r - x[i] * 2;
        ans    = std::min(ans, skill(rr, i + 1, n, x, y));
        swap(i, j);
    }
    return ans;
}

// 将seed变为偶回文数
inline int64_t evenEnlarge(int64_t seed)
{
    int64_t ans = seed;
    while (seed > 0) {
        ans = seed % 10 + ans * 10;
        seed /= 10;
    }
    return ans;
}

// 将seed变为奇回文数
inline int64_t oddEnlarge(int64_t seed)
{
    int64_t ans = seed;
    while (seed > 9) {
        seed /= 10;
        ans = ans * 10 + seed % 10;
    }
    return ans;
}

// 检查num是否在l,r范围内，且是否是回文数
inline bool check(int64_t num, int64_t l, int64_t r)
{
    auto isPalindrome = [](int64_t num) {
        int64_t offset = 1;
        while (num / offset >= 10) {
            offset *= 10;
        }
        while (num != 0) {
            if (num / offset != num % 10) return false;
            num = num % offset;
            num = num / 10;
            offset /= 100;
        }
        return true;
    };
    return l <= num && num <= r && isPalindrome(num);
}
}   // namespace

namespace lxj
{
// 现在有一个打怪类型的游戏，这个游戏是这样的，你有n个技能
// 每一个技能会有一个伤害，
// 同时若怪物小于等于一定的血量，则该技能可能造成双倍伤害
// 每一个技能最多只能释放一次，已知怪物有m点血量
// 现在想问你 [最少用几个技能] 能消灭掉他(血量小于等于0)
// 技能的数量是n，怪物的血量是m
// i号技能的伤害是x[i]，i号技能触发双倍伤害的血量最小值是y[i]
// 1 <= n <= 10
// 1 <= m、x[i]、y[i] <= 10^6
// 测试链接 : https://www.nowcoder.com/practice/d88ef50f8dab4850be8cd4b95514bbbd
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"
// 可以直接通过
inline int optimal(std::vector<int>& x, std::vector<int>& y, int m)
{
    int n   = x.size();
    int ans = skill(m, 0, n, x, y);
    return ans == MAX ? -1 : ans;
}

// 超级回文数(superpalindromesInRange1方法C++版本)
// 如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。
// 现在，给定两个正整数 L 和 R （以字符串形式表示），
// 返回包含在范围 [L, R] 中的超级回文数的数目。
// 1 <= len(L) <= 18
// 1 <= len(R) <= 18
// L 和 R 是表示 [1, 10^18) 范围的整数的字符串
// 测试链接 : https://leetcode.cn/problems/super-palindromes/
// 如下实现是课上讲的superpalindromesInRange1方法的C++版本，提交如下代码可以直接通过
constexpr int64_t MAX64 = ~(1ll << 63);
inline auto       superpalindromesInRange(std::string left, std::string right)
{
    int64_t l, r;
    std::from_chars(left.data(), left.data() + left.size(), l);
    std::from_chars(right.data(), right.data() + right.size(), r);

    std::vector<int64_t> sp;
    int64_t              limit = std::sqrt(r);
    int64_t              seed  = 1;
    int64_t              num   = 0;
    int                  ans   = 0;
    while (num < limit) {
        num = evenEnlarge(seed);
        if (num <= limit && num <= std::sqrt(MAX64) && check(num * num, l, r)) {
            ans++;
            sp.push_back(num * num);
        }
        num = oddEnlarge(seed);
        if (num <= limit && num <= std::sqrt(MAX64) && check(num * num, l, r)) {
            ans++;
            sp.push_back(num * num);
        }
        seed++;
    }
    struct result {
        int                  a;
        std::vector<int64_t> s;
    };
    std::sort(sp.begin(), sp.end());

    return result{.a = ans, .s = sp};
}

// 超级回文数打表法
inline int superpalindromesInRange2(std::string left, std::string right)
{
    std::vector<int64_t> sp{1ll,
                            4ll,
                            9ll,
                            121ll,
                            484ll,
                            10201ll,
                            12321ll,
                            14641ll,
                            40804ll,
                            44944ll,
                            1002001ll,
                            1234321ll,
                            4008004ll,
                            100020001ll,
                            102030201ll,
                            104060401ll,
                            121242121ll,
                            123454321ll,
                            125686521ll,
                            400080004ll,
                            404090404ll,
                            10000200001ll,
                            10221412201ll,
                            12102420121ll,
                            12345654321ll,
                            40000800004ll,
                            1000002000001ll,
                            1002003002001ll,
                            1004006004001ll,
                            1020304030201ll,
                            1022325232201ll,
                            1024348434201ll,
                            1210024200121ll,
                            1212225222121ll,
                            1214428244121ll,
                            1232346432321ll,
                            1234567654321ll,
                            4000008000004ll,
                            4004009004004ll,
                            100000020000001ll,
                            100220141022001ll,
                            102012040210201ll,
                            102234363432201ll,
                            121000242000121ll,
                            121242363242121ll,
                            123212464212321ll,
                            123456787654321ll,
                            400000080000004ll,
                            10000000200000001ll,
                            10002000300020001ll,
                            10004000600040001ll,
                            10020210401202001ll,
                            10022212521222001ll,
                            10024214841242001ll,
                            10201020402010201ll,
                            10203040504030201ll,
                            10205060806050201ll,
                            10221432623412201ll,
                            10223454745432201ll,
                            12100002420000121ll,
                            12102202520220121ll,
                            12104402820440121ll,
                            12122232623222121ll,
                            12124434743442121ll,
                            12321024642012321ll,
                            12323244744232321ll,
                            12343456865434321ll,
                            12345678987654321ll,
                            40000000800000004ll,
                            40004000900040004ll,
                            1000000002000000001ll,
                            1000220014100220001ll,
                            1002003004003002001ll,
                            1002223236323222001ll,
                            1020100204020010201ll,
                            1020322416142230201ll,
                            1022123226223212201ll,
                            1022345658565432201ll,
                            1210000024200000121ll,
                            1210242036302420121ll,
                            1212203226223022121ll,
                            1212445458545442121ll,
                            1232100246420012321ll,
                            1232344458544432321ll,
                            1234323468643234321ll,
                            4000000008000000004ll};

    int64_t l, r;
    std::from_chars(left.data(), left.data() + left.size(), l);
    std::from_chars(right.data(), right.data() + right.size(), r);

    int i = 0;
    int j = sp.size() - 1;
    while (sp[i] < l) {
        i++;
    }
    while (sp[j] > r) {
        j--;
    }
    return j - i + 1;
}
}   // namespace lxj

#endif